The present invention relates generally to data flow graph schemas. More specifically, the present invention relates to data flow graphs suitable for use in communication systems, such as downhole wireless communication systems.
Developed in the 1960's, data flow graphs (DFG) were used specifically to provide flexible, easy to program, interfaces for Digital Signal Processing (DSP) algorithms. Synchronous data flow graph (SDFG) schemas have been deployed for their flexibility and robustness in many different situations (for example, in chemical and nuclear plants, in aircraft flight control systems, cognitive radio and in spacecraft).
A typical SDFG consists of nodes or “actors” (corresponding to functional blocks) and connecting arcs or “edges” (indicating the passage of data “samples” from a first node to the next). SDFGs are typically directed graphs (the paths between nodes/actors are unidirectional). Each node receiving samples from one or more preceding nodes is “fired” or executes once they have input data available to process (e.g. when the number of samples received reaches a threshold level). The nodes deployed, the threshold levels and the arcs taken between nodes may each be considered “parameters” of the SDFG schema.
SDFGs support multiple arcs leaving or arriving at each node but this can lead to the problem of data deadlock (when two or more competing actions are waiting for the other to finish, and thus neither does). Consequently, graphs having multiple arcs may need to be re-parameterized and checked for deadlock.
Certain known SDFG schemas allow the parameters used to be altered and changed. These schemas, however, are typically hierarchical; groups of nodes and connecting arcs being clustered and considered as a single “supernode” for the purposes of a higher level in the hierarchy. Hierarchy is adopted to allow parallel execution of nodes. Where nodes (or supernodes) are executed in parallel, there arises a need to temporarily store output in asynchronous buffers. Parallelism and asynchronous buffering means these schemas also require deadlock checks. Furthermore, they do not provide for the safe destruction and rebuilding of parameters associated with the graph.
Further variations on the SDFG incorporate control arcs that aim to add the flexibility of procedural code to the model. Incorporation of control arcs (and subgraphs) adds considerable additional complexity, undermining the simplicity and efficiency of SDFGs.
Downhole conditions are hostile with unstable, difficult communication conditions and high temperatures. The high temperature environment, such as a deep well, restricts hardware computational resources to low speed processors with small amounts of on-board memory. Unstable communication channels (whether electromagnetic, acoustic or wired) or the need to prioritize data processing leads to the requirement for flexibility in managing resources as conditions change. There are therefore two key requirements for downhole communications and data processing; they are resource management and the dynamic instantiation of optimal data processing elements.
There is furthermore a need for functionality that can instantiate simple and efficient SDFGs ‘on the fly’ at run time, in a form where they can be safely built and destroyed.